\section{A passive ciphertext only attack on A5/1}

As mentioned earlier in this paper, the $A5/1$ differs from $A5/2$ in only one
aspect: By the way the clocking of each register is determined. $A5/1$ does not
have a fourth register, $R4$, that calculate the clocking.
Instead it uses the internal state of the three registers. $R1[8]$, $R2[10]$ and
$R3[10]$ are all fed into the clocking function and those register that agree
with the clocking bit, for instance. the output of the clocking function, are
clocked.
This means that we cannot simply guess $R4$ to determine the clocking of the
registers.

This passive attack requires the attacker only to receive data and not to
transmit any. This attack, as well as the attack described in the previous
sections utilises that the protocol applies error correction before the
encryption of the message. 

In the ciphertext only attack on $A5/2$, we created a function $H \cdot k$ of
the key-stream. This function can be expressed as the function $h(x)$ where x is
the initial state of the registers at the first frame. According to \rf{HandCipher}
this function can also be calculate from the ciphertext.

Now we define $h(x)$ to be:
\be{hfunction}
	h : \lbrace 0,1 \rbrace^{64} \rightarrow \lbrace 0,1 \rbrace^{64} 
\ee

since all the registers together contain 64 bits we take them as input, and we
let the output be an other 64 bit vector. We will get back to the output
length of the function when we talk about the time/memory/data trade-off attack
on $h(x)$

We would like to find he inverse of $h(x)$ such that it is possible to get the
initial state of the registers from the ciphertext. This is in fact a hard
problem, since that would involve reversing the $A5/1$ cipher i.e finding
$h^{-1}(y') = x'$ where $h(x') = y'$ as shown in \rf{Hx}.
\begin{figure}[htp]\label{Hx}
\centering
\includegraphics[scale=0.389]{Hx.png}
\caption{The $h$ function and its inverse}
\end{figure}

The way Barkan, Bahim and Keller does this is by a time/memory/data trade-off
that is described in \cite{bs}. This method involves a
pre-processing step and an online step. In the pre-processing they calculate
different paths from one starting state over some iterations of the function
$h(x)$ to an end state. In the online step, they use the data points given and
se if they can match one of those to some state in the precomputed matrix.

Let $N$ be the search space, for the $A5$-series we are looking for $K_c$ which
is 64 bits, so in our case $N = 2^{64}$.
The first step of the attack generates a $[m \times t]$ matrix where each row is
the paths of iterations of $h(x)$ $t$ times. The first column of the matrix is the
starting points for each path, and the last column is the endpoint for the path.
To cover the most paths without getting too many duplicated points in the
matrix, it is reasonable to let $m \cdot t^2 = N$, since the Birthday
paradox says that if we have $m \cdot t$ disjoint points and add $t$ more
points they will still, with high probability be disjoint if $t \cdot m
\cdot t \leq N$. The data saved from the pre-computation is the pairs consisting
of start and endpoints.

In the online step we are given is given $D + \log(N) - 1$ generated bits, it
then computes all the $D$ possible images \{$y_1, y_2,\ldots, y_D$\} where
$|y_j| = \log(N)$. Each of these $y_j$ are looked up in the precomputed table,
if a match is found we use the $x_j$ initial state and try to compute the rest
of key by running the generator from this initial state. If it is possible, we
know the initial state, and it is therefore possible to compute $K_c$ from
$x_i$.

The attack in \cite{bs} shows that the
threshold of success is on a time/memory trade-off curve where $T \cdot M^2
\cdot D^2 = N$ for $T$ being the number of times $h(x)$ is used in the online step.
The constraints for these variables are, according to (BS) $D^2 \leq T \leq N$.
This setup will give a success rate of at least 60\%. 

This attack uses the same idea as the ciphertext only attack on $A5/2$. It is
again the error correction applied before encryption that makes this attack
possible. The $A5/1$ algorithm is in fact harder to break than $A5/2$, since we
cannot guess all the possible $2^{16}$ values of $R4$ since it is not used,
but as shown with the time/memory/data trade-off attack, it is possible to break
the encryption and obtain $K_c$ if you have enough computing power to do the
pre-processing and enough space. 
